// Copyright (C) 2010 and onwards Harik Shazeer Labs
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// 
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Authors: Noam Shazeer and Georges Harik

#ifndef _OBJECTS_H_
#define _OBJECTS_H_

#include "util.h"

class Object;

// globally for SYMBOLS, SPECIALS and NATIVE_FUNCTIONS
extern map<string, Object *> STRING_OBJECT;
extern map<Object *, string> OBJECT_STRING;

enum ObjectType {
  BOXED,
  // disabled  BYTE_ARRAY_TYPE,      // binary block data
  INTEGER,         // unboxed 61 bit
  SYMBOL,          // user defined symbols (usually used for variables)
  SPECIAL,         // special forms like IF DOTIMES
  CONSTANT,        //things like NIL and T
  NATIVE_FUNCTION, // + - ...
  CHAR,            // character types
  // boxed types
  ARRAY_TYPE,      // data represents a size and a start Object**
  FREE_SPACE,     // should never be referenced.  Used for deleted objects
};

void CheckObjectSizes();

// Flags for the top part of type_
#define MUTABLE_OBJECT 0x100    // is this array mutable
#define REACHABLE_OBJECT 0x200  // used in garbage collection

// Boxed objects: Arrays or Byte Arrays
struct Object {
  // low byte is type.  second byte is flags. High 6 bytes are length
  // byte 0: type
  // byte 1: flags
  // byte 2: unused
  // bytes 3-7: length
  uint64 object_info_;
  uint64 hash_;
  uint64 garbage_;
  uint64 node_count_; // maintained for immutable arrays. 0 means >= 2^60

#define link__ garbage_
#define new_location__ garbage_
  
  // Constructor
Object() : object_info_(0), hash_(0), node_count_(0) {}

  // accessors
  void ZeroOut() { object_info_ = 0;}
  ObjectType GetType() { return ObjectType(object_info_ & 0xff); }
  void SetType(uchar type) 
  { object_info_ = (object_info_ & 0xffffffffffffff00ull) | type; }
  bool GetFlag(uint64 flag) { return object_info_ & flag; }
  void SetFlag(uint64 flag) { object_info_ |= flag; }
  void RemoveFlag(uint64 flag) { object_info_ &= ~flag; }
  void SetLength(uint64 length) 
  { object_info_ = (object_info_ & 0xffffffull) | (length << 24); }
  uint64 GetLength() const { return object_info_ >> 24; }

  // Array accessors
  uint64 ArraySize() const { return GetLength(); }
  // Object ** & ArrayData() { return *((Object***)(&data_)); }
  Object ** ArrayData() { return (Object **)(this + 1); }
  Object * & Ref(int i) { return ArrayData()[i]; }
  Object * & Car() {return ArrayData()[0];}
  Object * & Cdr() {return ArrayData()[1];}
  Object * & First() {return ArrayData()[0];}
  Object * & Second() {return ArrayData()[1]->ArrayData()[0];}
  Object * & Third() {return ArrayData()[1]->ArrayData()[1]->ArrayData()[0];}

  // Dealing with byte arrays
  // uint64 ByteArraySize() { return GetLength(); }
  // uchar *& ByteArrayData() { return *((uchar **)(ArrayData())); }
  
  // Simple checks and modifiers
  bool IsReachable() { return GetFlag(REACHABLE_OBJECT); }
  bool IsMutable() { return GetFlag(MUTABLE_OBJECT); }
  void MakeImmutable() { 
    if (IsMutable()) {
      RemoveFlag(MUTABLE_OBJECT);
      hash_ = 0;
    }
  }
  void ComputeNodeCount();
};

inline ObjectType GetUnboxedType(Object *p) {
  return (ObjectType)((int64)p & 0x7);  
};

// Getting types of Objects. Uses boxing / unboxing techniques
// Depending on low 3 bits:
// 0 - pointer to an Object structures. Bits 0-15 of type_ are type.
// >0 : the type
inline ObjectType GetType(Object*p) {
  if (GetUnboxedType(p) == BOXED) return p->GetType();
  return GetUnboxedType(p);
}

inline bool IsCons(Object *o) {
  return ((GetType(o) == ARRAY_TYPE) && (o->ArraySize() == 2));
}



// An array object that is specialized to hold only CHAR
bool IsString(Object *p);

// Fast access to some aspects of objects
inline uint64 GetEnumValue(Object*p) { return ((uint64)p >> 16); }
inline bool IsUnboxed(Object *p) { return (uint64)p & 7; }
inline bool IsBoxed(Object *p) { return !IsUnboxed(p); }
inline bool IsMutable(Object * o) {
  return IsBoxed(o) && o->IsMutable(); 
}
inline int64 GetInteger(Object *p) { return (int64)p >> 3; }
inline uchar GetChar(Object *p) { return GetEnumValue(p); }

// returns true if there was any effect
inline bool MakeReachable(Object *o) {
  if (!o) return false;
  if (!IsBoxed(o)) return false;
  if (o->GetFlag(REACHABLE_OBJECT)) return false;
  uint64 old_val = 
    __sync_fetch_and_or(&(o->object_info_), REACHABLE_OBJECT); 
  return !(old_val & REACHABLE_OBJECT);
}

inline bool WasDeleted(Object *o) {
  return o && (GetType(o) == FREE_SPACE);
}

inline Object * NewLocation(Object *o) {
  if (!o) return NULL;
  if (!IsBoxed(o)) return o;
  if (GetType(o) == FREE_SPACE) return NULL;
  return (Object *) o->new_location__;
}

// Convert an Object to a raw string if it is a string
string StringToCPPString(Object * p);

// Getting the nodecount of an object
inline uint64 NodeCount(Object *p) { 
  if (IsBoxed(p)) return p->node_count_; 
  return 1; 
}

bool DepthLessThan(Object *p, int64 max_depth);

// This object and all descendants -> result
void AllSubnodes(Object *p, vector<Object *> *result);

uint64 Hash(Object *p);

inline uint64 ArrayHashStart() { return 0xdeadbeef12345678ull; }
inline uint64 ArrayHashNext(uint64 last_hash, Object * new_element) {
  return Fingerprint(Hash(new_element), last_hash);
}
inline uint64 ArrayHash(Object **a, uint64 length) {
  uint64 ret = ArrayHashStart();
  for (uint64 i=0; i<length; i++) ret = ArrayHashNext(ret, a[i]);
  return ret;
}

// This may be better in the .cc file
inline uint64 Hash(Object *p) {
  CHECK(p);
  if (IsUnboxed(p)) return (uint64)p * 91847218953211ull;
  return p->hash_;
}

// Hashing parts of a stack of Object *s
inline uint64 HashStack(Object **begin, Object **end) {
  uint64 ret = 12345;
  for (Object **run = begin; run!=end; run++) {
    ret = Fingerprint(Hash(*run), ret);
  }
  return ret;
}

// A comparator for Object * to compare by their hashes
struct ObjectHashLess {
  bool operator() (Object * a, Object * b) {
    return (Hash(a) < Hash(b));
  }
};

// Making some non-allocated types of Objects
Object * MakeSymbol(string name);
Object * MakeConstant(string name);
inline Object *MakeEnum(ObjectType type, uint64 value) {
  return (Object *) (type + (value << 16)); }
inline Object *MakeCharacter(uchar c) {
  return MakeEnum(CHAR, c); }
inline Object *MakeInteger(int64 i) {
  return (Object*)((i << 3) + INTEGER); }

// These also bind enums or symbols to names 
Object * AddEnum(ObjectType t, int value, string name);
Object * GetObjectOrMakeSymbol(string name);

inline Object * NextObject(Object * o) {
  CHECK(IsBoxed(o));
  switch (GetType(o)) {
  case ARRAY_TYPE:
    return (Object *) (o->ArrayData() + o->ArraySize());
  case FREE_SPACE:
    // In case of free space, length includes the object itself as well
    return (Object *) ( ( (uint64 *)o) + o->GetLength());
  default:
    CHECK(false);
    return NULL;
  }
}

// Object size in words
inline uint64 ObjectWordSize(Object * o) {
  CHECK(IsBoxed(o));
  return ((uint64*) NextObject(o) - (uint64*) o); 
}

// returns the previous size in words of the object that was freed.
inline uint64 ReplaceWithFreeSpace(Object *o) {
  uint64 ows = ObjectWordSize(o);
  o->SetType(FREE_SPACE);
  o->SetLength(ows);
  return ows;
}

// returns the old integer value of *o
// coerces NULL into 0
inline int64 SyncFetchAddIntegerObject (Object ** o, int64 increment) {
  while (1) {
    Object * old_val = *o;
    if (old_val == NULL) {
      if (__sync_bool_compare_and_swap(o, old_val, MakeInteger(increment))){
	return 0;
      }
    } else if (GetUnboxedType(old_val) == INTEGER) {
      if (__sync_bool_compare_and_swap(o, old_val, MakeInteger(GetInteger(old_val) + increment))) {
	return GetInteger(old_val);
      }
    } else return 0;
  }
  /*
  uint64 * u = (uint64*)o;
  __sync_fetch_and_or(u, 1);
  return GetInteger((Object *)__sync_fetch_and_add(u, (increment << 3) ));
  */
}

#endif
